package 力扣.堆;

import java.util.*;

public class 前k个高频元素347 {
    public static void main(String[] args) {
        int[] ints = {1,1,1,2,2,3};
        int k = 2;
        int[] nums = topKFrequent(ints, k);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 本质上还是TOPK问题，只不过多了查找频率这一步。
     * 极小堆+哈希表：出现频率最少的方法最上面，堆的size = k,大于size则出队
     */
    public static int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        //计算每个元素出现的次数
        for (int num:nums) {
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }
        // 第一个元素：元素本身  第二个元素：元素出现的次数
//        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {//通过重写抽象类Comparator中的compare方法可以更改比较方式
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                return  o1[1] - o2[1];// o1 减去 o2 ：则是小根堆
//            }
//        });
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {//通过重写抽象类Comparator中的compare方法可以更改比较方式
            @Override
            public int compare(Integer o1, Integer o2) {
                return  hashMap.get(o1) - hashMap.get(o2);// o1 减去 o2 ：则是小根堆
            }
        });
        Set<Integer> set = hashMap.keySet();
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()){
            Integer key = iterator.next();
//            Integer value = hashMap.get(key);
//            int[] te = new int[]{key,value};
            pq.offer(key);
            if (pq.size() > k){
                pq.poll();
            }
        }
        int[] ans = new int[k];
        int i = 0;
        while (!pq.isEmpty()){
//            ans[i] = (int)pq.poll()[0];
            ans[i] = pq.poll();
            i++;
        }
        return ans;
    }
}
